//n! mod p
int factmod (int n, int p) {
	long long res = 1;
	while (n > 1) {
		res = (res * powmod (p-1, n/p, p)) % p;
		for (int i=2; i<=n%p; ++i)
			res = (res * i) % p;
		n /= p;
	}
	return int (res % p);
}